from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if target < nums[0] or target > nums[-1]:
            return -1
        i, j = 0, len(nums)-1
        while i <= j:
            m = i + (j-i)//2
            if nums[m] == target:
                return m
            elif nums[m] < target:
                i = m + 1
            else:
                j = m - 1
        return -1


if __name__ == '__main__':
    x = Solution()
    print(x.search([-1,0,3,5,9,12], -1))